This invention relates to sensing devices and, in particular, to sensing devices which minimize low frequency noise and the generation of detectable aliases.
Any device used to sample a signal has a maximum sampling rate that is determined by the physical characteristics of the device. This maximum sampling rate is related to the bandwidth of the device.
If a signal is sampled at a constant sampling rate and at uniformly and equally spaced intervals, the high frequency variations of the signal that occur between successive samples cannot be correctly detected. The power that corresponds to the undetected signal variations will be conflated with power that corresponds to lower frequency variations, thereby resulting in distortions of the sampled signal values. These distortions are called aliases.
If a signal does not contain power in frequencies greater than one-half the sampling rate, it can be reconstructed exactly from its sampled values. Conversely, if the signal does contain power in frequencies greater than one-half the sampling rate, the signal can not be reconstructed from its sampled values. Moreover, in the latter case, aliases are often significant features of the signal, resulting in false and often misleading information being incorporated in the signal.
The phenomenon of aliasing can be understood from a study of FIGS. 1-4. In FIG. 1, a continuously varying signal f(t) is applied to an input terminal 10 which is connected to an elongated switch segment 12 A switch arm 14, which rotates at a sampling rate of f.sub.c times per second, makes contact with the segment 12 for .lambda. seconds during each rotation. As a result, a sampled version of f(t), output signal f.sub.s (t), is applied across the input terminals 16, 18 of a transmitting system 20. In practice, the sampling process would be carried out electronically by switching the signal on and off but, for the purpose of explanation, a mechanical switch has been shown in FIG. 1.
A typical signal f(t), which varies continuously as a function of time t, is shown in FIG. 2a. This signal is sampled at the rate f.sub.c such that the sampling interval T=1/f.sub.c is much greater than the sampling time .lambda.. The sampled output f.sub.s (t) is shown in FIG. 2(b).
If the signal f(t) has no frequency components in its spectrum beyond f=B, where B is the bandwidth of f(r), the magnitude of its Fourier transform F(.omega.) would be as shown in FIG. 2(c), where .omega.=2.pi.f.
The sampled signal f.sub.s (t) can be represented in terms of f(t) by the relation EQU f.sub.s (t)=f(t)s(t),
where s(t) is a periodic switching function consisting of a series of pulses of unit amplitude, width .lambda. and period T=1/f.sub.c. This switching function is shown in FIG. 3.
The Fourier transform F.sub.s (.omega.) of the sampled signal f.sub.s (t) is given by the convolution of the Fourier transforms F(.omega.) and S(.omega.) of the signal f(t) and the switching function s(t), respectively. It is shown in FIG. 4 where the abscissa is plotted in units of frequency f and the ordinate is the Fourier transform F.sub.s (.omega.).
It can be seen from the amplitude spectrum of FIG. 4 that an input signal f(t) which does not contain frequencies higher than B=f.sub.c /2 can be filtered from f.sub.s (t) by the use of a low pass filter that cuts off sharply before reaching the frequency spectrum centered at f.sub.c. However, if the speed with which switch arm 14 rotates is decreased, the frequency f.sub.c and all its harmonics close in on one another and eventually the spectral components of FIG. 4 overlap and merge.
In particular, the component F(.omega.-.omega..sub.c), centered about f.sub.c, would merge with the unshifted F(.omega.) term centered about the origin. It would then be impossible to separate out F (.omega.), and consequently f(t) could not be separated from f.sub.s (t). The distortions resulting from these overlapping spectra caused by taking samples at too widely spaced intervals are the aliases defined above. The limiting frequency at which F(.omega.) and F(.omega.-.omega..sub.c) merge is F.sub.c =2B, which is called the Nyquist sampling rate.
Next, considering the nature of images, an image is a distribution of light or other form of radiation over a surface, generally a plane rectangle such as the face of the cathode ray tube of a television receiver. Television receivers effectively display a sampled version of the image recorded by a video camera on 480 horizontal scan lines that are clearly visible to the eye when one is close to the television screen being viewed. The television picture does not accurately discriminate spatial variations in the vertical direction that correspond to distances less than twice the distance between successive scan lines, that is, of spatial frequencies greater than half the 480 line per screen sampling rate of the standard NTSC American broadcast television. This results in aliases which appear as moire patterns when objects such as striped shirts, which exhibit spatial frquency variations greater than the Nyquist rate, are sampled by the video camera and reproduced by the receiver.
Because the bandwidth of the television broadcast signal is limited, discrimination of variations in the horizontal direction, along the scan lines, is also limited, and contributes to the creation of aliases.
Modern video cameras often use a rectangular array of regularly spaced light sensors, such as uniformly distributed arrays of charge-coupled devices (CCD), to capture an image and either store, or broadcast, it for further distribution to television receivers. The limited rate of spatial sampling of present CCD-imaging array video cameras results in aliases when certain scenes are imaged. Aliases in general, and image aliases in particular, can produce striking artifacts that cannot alWays be distinguished from real features of the signal. In addition to causing confusion, aliases may result in errors which can be costly, time-consuming or both.
As an example, consider a computer-generated image consisting of a square array of 512.times.512=262,144 picture elements, called "pixels," each of which is a gray level specified by an 8-bit code. The code 00000000 corresponds to black and the code 11111111 to the brightest light level that can be produced by the imaging apparatus. Thus there are 2.sup.8 =256 distinct representable shades of gray, ranging from black to white. Spatial variations that occur within distances less than the width of a pixel cannot be accurately represented by this image.
If such an image were sampled by a device that measures the gray level of pixels that form a square lattice consisting of every fifth pixel in both the horizontal and vertical direction, then this uniformly sampled version of the image would consist of about 10,000 values and contain only about 4% of the amount of information in the original image. Gray levels for intermediate pixels could be interpolated, for instance, by linear or by Gaussian interpolation. However, the interpolated result could show numerous strong alias artifacts.
It is not possible to both eliminate aliases and permit faithful reconstruction of the image signal without increasing the rate of spatial sampling so that all power in the signal lies in spatial frequencies that are less than the Nyquist frequency, i.e., less than one-half the sampling frequency. However, if the sampling frequency is held fixed, then the effects of aliasing can be diminished or even eliminated in special cases, either by (1) bandlimiting the signal before sampling in order to eliminate high frequency power (e.g., by blurring the image before sampling), or (2) distributing the power that arises from the high spatial frequencies throughout the spatial frequencies that are less than the Nyquist frequency, rather than concentrating that power among a small number of low frequencies or ranges of low spatial frequencies. The redistributed power is perceived as noise rather than as aliases in the image.
It has been shown that aliases can be eliminated entirely in the statistical sense for a one-dimensional signal by sampling the signal at non-uniform intervals if the non-uniform intervals are chosen from a suitable probability distribution. In particular, it has been shown in Shapiro et al., "Alias-free sampling of random noise." J. Soc. Industrial and Appl. Math. 80 (1960), p. 225-248, that by selecting the sampling points at random from the uniform probability distribution until the desired average sampling rate is obtained, aliases are traded for a statistically uniform distribution of noise throughout the frequency domain. This sampling process is referred to as Poisson sampling because the distribution of the length of the intervals between successive samples is the Poisson distribution of statistical theory.
A sampled image is often intended to convey information about some real scene that it represents. In this case it is frequently important for the viewer to know that organized structures that appear in the image are faithful replicas of corresponding structures in the original scene, insofar as the bandwidth of the imaging system permits them to be represented. In such situations it is generally more helpful to the viewer if high frequency spatial information corresponding to power above the Nyquist frequency is represented by noise rather than by alias artifacts.
The degree to which a particular sampling process will produce aliases or noise can be determined by an analysis of the Fourier transform of the sampling distribution according to standard and well known techniques. FIGS. 5(a) and 5(b) show such an analysis for a uniform sampling of a one-dimensional signal. FIG. 5(a) displays the sampling function s(t), which consists of a uniformly spaced sequence of sampling spikes each of which is the numerical approximation of a Dirac delta function. The Fourier transform of the sampling function s(t) is F(.omega.)=.vertline.F(.omega.).vertline..epsilon..sup.-j.theta.(.omega.), where .theta.(.omega.) is the phase of the Fourier transform of the sampling function measured in radians. FIG. 5(b) shows the power spectrum .vertline.F(.omega.).vertline..sup.2, that is, the square of the absolute value of the Fourier transform of the sampling function exhibited in FIG. 5(a). In this frequency domain representation of the sampling function, a frequency of zero Hz corresponds to the coordinate that lies under the central peak of FIG. 5(b), and the Nyquist frequency corresponds to the coordinates labelled -f.sub.c and f.sub.c.
Aliases are produced by the sampling function when the Fourier transform of the signal extends beyond the Nyquist frequency, i.e., when it overlaps a copy of itself that has been shifted so as to be centered over the peaks in FIG. 5(b) adjacent to the central peak at zero Hz. The magnitude or strength of the alias produced by a peak is proportional to the product of the power in the signal at the frequency of the peak and the magnitude of the peak itself. Since the peaks in the magnitude of the Fourier transform of a uniform sampling function are all of nearly equal height, and would be exactly the same height if the number of sample points were infinite, the magnitude of the aliases depends primarily on the amount of power in the signal at the frequency of the peaks.
This analysis of the uniform sampling process that corresponds to FIGS. 5(a) and 5(b) shows that it will produce strong aliases for signals that have power in frequencies greater than half the sampling rate.